package com.note.feng.leetcode.algorithms.easy.twelve;

import java.util.HashMap;
import java.util.Map;

public class ThousandTwoHundredNinetyNine {

    /**
     * 1299. 将每个元素替换为右侧最大元素
     * 给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
     *
     * 完成所有替换操作后，请你返回这个数组。
     *
     * 示例 1：
     *
     * 输入：arr = [17,18,5,4,6,1]
     * 输出：[18,6,6,6,1,-1]
     * 解释：
     * - 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
     * - 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
     * - 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
     * - 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
     * - 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
     * - 下标 5 的元素 --> 右侧没有其他元素，替换为 -1
     * 示例 2：
     *
     * 输入：arr = [400]
     * 输出：[-1]
     * 解释：下标 0 的元素右侧没有其他元素。
     *
     * 提示：
     *
     * 1 <= arr.length <= 104
     * 1 <= arr[i] <= 105
     */

    /**
     * 解法：倒叙遍历
     * 1、倒序遍历，找到每个元素右边的最大值
     * 2、遍历数组，替换为右侧的最大值
     * @param arr
     * @return
     */
    public int[] replaceElements(int[] arr) {
        if(arr.length == 1){
            return new int[]{-1};
        }
        int len = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(len - 1, -1);
        map.put(len - 2, arr[len - 1]);
        for (int i = len - 3; i >= 0; i--) {
            map.put(i - 1, Math.max(arr[i + 1], map.get(i + 2)));
        }
        int [] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = map.get(i);
        }
        return res;
    }
}
